Search results for "binary relation"
showing 10 items of 11 documents
Unit Operations in Approximation Spaces
2010
Unit operations are some special functions on sets. The concept of the unit operation originates from researches of U. Wybraniec-Skardowska. The paper is concerned with the general properties of such functions. The isomorphism between binary relations and unit operations is proved. Algebraic structures of families of unit operations corresponding to certain classes of binary relations are considered. Unit operations are useful in Pawlak's Rough Set Theory. It is shown that unit operations are upper approximations in approximation space. We prove, that in the approximation space (U, R) generated by a reflexive relation R the corresponding unit operation is the least definable approximation i…
An Algebraic Approach to Knowledge Representation
1999
This paper is an attempt to apply domain-theoretic ideas to a new area, viz. knowledge representation. We present an algebraic model of a belief system. The model consists of an information domain of special kind (belief algebra) and a binary relation on it (entailment). It is shown by examples that several natural belief algebras are, essentially, algebras of flat records. With an eye on this, we characterise those domains and belief algebras that are isomorphic to domains or algebras of records. For illustration, we suggest a system of axioms for revision in such a model and describe an explicit construction of what could be called a maxichoise revision.
SEA presidential address: Group connectivity and cooperation
2011
A model-free methodology is used for the first time to estimate a daily volatility index (VIBEX-NEW) for the Spanish financial market.We use a public data set of daily option prices to compute this index and showthat daily changes in VIBEXNEW display a negative, tight contemporaneous relationship with IBEX daily returns, contrary to other common volatility indicators, as an implied volatility indicator or a GARCH(1,1) conditional volatility model. This relationship is approximately symmetric to the sign on VIBEX-NEW changes and asymmetric to the IBEX-35 returns sign, which make it clearly a suitable volatility index for the Spanish stock market. We also examine the relationship between curr…
Efficient evaluation for a subset of recursive queries
1991
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…
Knowledge Representation in Extended Pawlak’s Information Systems: Algebraic Aspects
2002
The notion of an information system in Pawlak's sense is extended by introducing a certain ordering on the attribute set, which allows to treat some attributes as parts of others. With every extended information system S associated is the set K(S) of those pieces of information that, in a sense, admit a direct access in S. The algebraic structure of the "information space" K(S) is investigated, and it is shown, in what extent the structure of S can be restored from the structure of its information space. In particular, an intrinsic binary relation on K(S), interpreted as entailment, is isolated, and an axiomatic description of a knowledge revision operation based on it is proposed.
Elementary Action Systems
2015
This chapter expounds basic notions. An elementary action system is a triple consisting of the set of states, the transition relation between states, and a family of binary relations defined on the set of states. The elements of this family are called atomic actions. Each pair of states belonging to an atomic action is a possible performance of this action. This purely extensional understanding of atomic actions is close to dynamic logic. Compound actions are defined as sets of finite sequences of atomic actions. Thus compound actions are regarded as languages over the alphabet whose elements are atomic actions. This chapter is concerned with the problem of performability of actions and the…
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
Unification of Graphs and Relations in Mizar
2020
Summary A (di)graph without parallel edges can simply be represented by a binary relation of the vertices and on the other hand, any binary relation can be expressed as such a graph. In this article, this correspondence is formalized in the Mizar system [2], based on the formalization of graphs in [6] and relations in [11], [12]. Notably, a new definition of createGraph will be given, taking only a non empty set V and a binary relation E ⊆ V × V to create a (di)graph without parallel edges, which will provide to be very useful in future articles.
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Performability of Actions
2021
AbstractAction theory may be regarded as a theoretical foundation of AI, because it provides in a logically coherent way the principles of performing actions by agents. But, more importantly, action theory offers a formal ontology mainly based on set-theoretic constructs. This ontology isolates various types of actions as structured entities: atomic, sequential, compound, ordered, situational actions etc., and it is a solid and non-removable foundation of any rational activity. The paper is mainly concerned with a bunch of issues centered around the notion of performability of actions. It seems that the problem of performability of actions, though of basic importance for purely practical ap…